In recent years, problems relating to the reliability of commodities or the like provided to consumers, e.g., motor vehicle recall problems and commodity imitation problems have been perceived. The establishment of traceability of products and commodities (hereinafter referred to as “items”) has attracted attention as a chief solution to these problems. Traceability is defined as the “ability to trace the history, application, or location of what is under consideration” (ISO9000: 2000). By a traceability technique, information can be obtained, for example, as to by whom a product was produced and which distribution channel the product was passed through. However,when consideration is given to use of this information among domains between which no trust-based relationship is established, there is a need for a mechanism for assuring the authenticity of the obtained information. A signature method is being generally used as a mechanism for assuring the authenticity of information.
Published Unexamined Patent Application No. 2004-94510 illustrates an example of a grapple with a challenge on assurance of the authenticity of information for traceability. In this example, electronic signatures are included in shipment and buying forms used in commodity distribution to enable verification of channels for commodity distribution. To be more specific, a label writer or the like having an alteration prevention function using a bar code or a two-dimensional code in each form is described.
In a traceability target area, a large amount of items are ordinarily distributed. It is, therefore, supposed that if a signature is written on each individual item, the cost of computation of signatures and verification of the signatures and the amount of signature data itself will considerably increase. Also, when an entity finally receiving a commodity (a being constituting a channel through which an item is passed will be hereinafter referred to as “entity”) verifies the entire distribution channel through which the item has passed, it is necessary for the entity to verify signatures written on a shipment form at the time of receiving by inquiring of an agency which certifies the authenticity of all entities concerned with the item. Consequently, an increased number of events of inquiry about entities occur and there is a problem relating to convenience at the time of verification.
A simple method for verifying passage of items through a plurality of entities is conceivable in which each entity writes its signature with respect to IDs for the items (assuming that a unique ID is attached to each item), and the subsequent entity writes its signature on the former signature in a multiple signature manner. However, the cost of computation for signatures and verification of the signatures is high, and this method is not practical in a case where the number of distributed items is large.
To improve the efficiency in a simple way, a process may be performed in which, when a plurality of items are sent from an entity to subsequent entities, the items are treated as one item group and each entity writes its signature with respect to the item group in a multiple signature manner. In this case, performing signature computation one time in each entity with respect to the plurality of items suffices. Also, performing signature verification the number of times corresponding to the number of entities through which the item group has passed suffices (assuming that the number of entities through which the items to be distributed are passed is sufficiently small relative to the number of the distributed items).
A situation where three items with IDs I1, I2, and I3 are passed via three entities A, B, and C will be considered by way of example. When A sends the items to B, it writes a signature SigA (I1, I2, I3) with respect to the entire item group formed by combining I1, I2, and I3. SigA (M) represents a signature written by using an ordinary signature schema with respect to a message M by the entity A. The entity B then receives it, writes a signature SigB (SigA (I1, I2, I3)) and sends it to C together with A's signature and the items. The entity C can verify A's signature from the received items I1, I2, I3 and can verify B's signature from the verified A's signature. Thus, the entity C can verify the entity path through which the items have passed.
This method, however, does not permit change of the combination of items constituting the item group, (e.g., B changing the item group delivered from A to B by selecting several ones of the delivered items in the item group, newly adding an item to the item group and sending the item group to C. For example, in a case where there is a need to change the composition of items to be delivered from B to C to I2, I3, and I4, C (verifier) that will receive the items cannot verify A's signature if I1, does not exist.